#include <iostream>
using namespace std;
struct Thing {
    string name;
    int weight;
    int value;

    Thing(string n, int w, int v) {
        name = n;
        weight = w;
        value = v;
    }

    Thing() {
        name = "";
        weight = 0;
        value = 0;
    }
};

int backpack(int packCapacity, Thing *thing, int thingCount) {
    int minWeight = thing[0].weight;
	//找出物品中重量最小的物品 
    for (int i = 1; i < thingCount; ++i)
    {
        int curWeight = thing[i].weight;
        if (curWeight < minWeight) {
            minWeight = curWeight;
        }
    }
	//如果背包所承重小于物品的最小重量，则返回-1 
    if (packCapacity < minWeight) {
        cout << "The capacity of package " 
             << packCapacity << " is less than the minimum weight of thing " 
             << minWeight << endl;
        return -1;
    }
    //创建二维表格，横轴是物品，纵轴是包能放入的物品的重量
    int weightCount = packCapacity + 1;
    int** dpArray = new int*[thingCount]();
    for (int i = 0; i < thingCount; ++i) {
        dpArray[i] = new int[weightCount];
    }
    // 填充表格
    for (int i = 0; i < thingCount; ++i)
    {
        // 记录放入背包物品的重量和价值
        int curWeight = thing[i].weight;
        int curValue = thing[i].value;
        for (int w = minWeight; w < weightCount; ++w)
        {
            // 记录不放入当前物品的情况下，放入背包物品能够达到的最大价值
            int preTotalValue= 0;

            if (i > 0) {
                preTotalValue = dpArray[i - 1][w];
            }
            // 记录放入当前物品的情况下，放入背包物品能够达到的最大价值
            int curTotalValue = 0;
            // 如果当前物品能够放入背包，记录下物品的价值
            if (w >= curWeight) {
                curTotalValue = curValue;
            }
            // 如果放入当前物品后背包还能放入其它物品，且确实还有其它物品，加上剩余的小背包能够放入物品的最大价值
            if ( w > curWeight && i > 0 ) {
                curTotalValue += dpArray[i-1][w - curWeight];
            }
            // 找出放入当前物品和不放入当前物品情况下，放入背包的物品能够达到的最大价值，更新最大价值 
            int maxTotalValue = preTotalValue;
            if (maxTotalValue < curTotalValue) {
                maxTotalValue = curTotalValue;
            }
            // 记录下放入当前物品后，能够放w磅物品的背包能够放入物品的最大价值 
            dpArray[i][w] = maxTotalValue;
        }    
    }
    //记录下最终的最大价值
    int maxValue = dpArray[itemCount - 1][weightCount - 1];
    for (int i = 0; i < thingCount; ++i) 
	{
        delete [] dpArray[i];
    }
    delete [] dpArray;
    return maxValue;
}
int main() {
    int packCapacity = 6;
    Thing thing[] = {     
        Thing("水", 3,10),
        Thing("书",1,3),
        Thing("食物",2,9),
        Thing("夹克", 2,5),
		Thing("相机",1,6) 
    };
    int thingCount = sizeof(thing)/sizeof(Thing);
    int maxValue = 0;
    maxValue = backpack(packCapacity, thing, thingCount);
    if (maxValue > 0) {
        cout << "最大价值是： " << maxValue << endl;
    }    
}
